\raggedbottom

\section{基于树形索引的$k$近邻查询技术}\label{sec:3}
如今在日常生活中充斥着诸如图像、音频、视频等多媒体信息。这些信息在传输、存储时通常以高维向量的形式表示，因而如今常见的图片检索、文档检索、听歌识曲等功能都可以抽象成在样本空间中查找某个高维向量的$k$近邻问题。然而随着数据规模和数据维度的增加，在样本空间中检索向量的$k$近邻花费的时间将呈指数增长，因而如何从数据规模大、数据维度高的样本空间中快速检索到高维向量的$k$近邻是大数据领域的一个热点问题。

\subsection{引言}
$k$近邻查询技术应用广泛，可用于分类、模式识别、推荐和数据压缩等领域，这里用一个分类问题来说明$k$近邻查询技术的应用。如图~\ref{fig:knnClassification}所示，根据$k$近邻查询技术实现了对查询点$q$（蓝色方块）的分类。基于$k$近邻查询技术的分类依据样本空间中已知类别的数据点（红色三角和绿色圆圈）来判断$q$应该属于A类还是属于B类。当$k=1$时，仅考虑距离查询点最近的样本点（绿色圆圈），认为查询点$q$与其距离最近的样本点属于同一类，即查询点$q$属于A类。当$k=3$时，考虑范围扩大到了距离查询点$q$最近的3的样本点（2个绿色圆圈，1个红色三角），查询点$q$应属于$k$近邻中的多数类，即查询点$q$属于A类。

\begin{figure}[htb]
\centering
\includegraphics[width=0.35\linewidth]{Thesis/content/FIG/Three/knnClassification.eps}
\bicaption{用$k$近邻查询实现分类}{Example of $k$NN Search for Classification}
\label{fig:knnClassification}
\end{figure}
\newpage

当然，计算$k$近邻最简单的方式就是扫描整个样本空间中的数据点，依次计算样本空间中的数据点与查询点之间的相似度，排序后得到查询点的$k$近邻。然而随着数据规模、数据维度的增长，这将会造成$k$近邻查询效率的迅速下降。如何通过索引结构合理的组织数据点，从数据规模大、数据维度高的样本空间中快速检索到$k$近邻将是本文主要讨论的内容。

在Multi-probe~LSH\cite{DBLP:conf/vldb/LvJWCL07}中认为一个理想的$k$近邻查询技术应当具备查询时间短、索引空间小、查询结果准确的特点。但当前三种主流的$k$近邻查询技术：1）基于图的$k$近邻查询技术~\cite{DBLP:journals/is/MalkovPLK14,DBLP:journals/pami/MalkovY20,DBLP:conf/sigmod/WuJZ14}；2）基于局部敏感哈希的$k$近邻查询技术~\cite{DBLP:conf/stoc/IndykM98,DBLP:journals/pvldb/SatuluriP12,DBLP:journals/pami/GongLGP13}；3）基于树的$k$近邻查询技术~\cite{DBLP:journals/cacm/Bentley75,DBLP:conf/bmvc/LeibeMS06,DBLP:reference/gis/HadjieleftheriouMTT17,DBLP:conf/vldb/SakuraiYUK00,CHEN2019145}都不能同时满足查询时间短、索引空间小、查询结果准确。基于图的$k$近邻查询技术尽管在查询时间、查询结果的准确率上表现都较为突出，但在索引构建过程中需要花费大量的时间建立$k$近邻图，此外随着数据规模增长索引体积也会随之快速增长。基于局部敏感哈希的$k$近邻查询技术简单高效，在一定程度上有理论保证，但由于索引结构较大不具备扩展性。基于树的$k$近邻查询技术在低维空间中的表现优异，但随着数据维度的增加索引结构的性能迅速下降，甚至产生“维数诅咒”现象。除了由于查询技术本身的缺陷外，现阶段的$k$近邻查询技术都是静态的，索引结构一旦建立，相同的查询点都会得到相同的$k$近邻结果。也就是说，即使查询点通过索引结构获得的结果是糟糕的，当再有相同的查询点通过索引结构仍然会返回相同的、糟糕的结果。

鉴于上述问题，本章提出了一种简单高效的$k$近邻查询技术。具体来说，本章通过一种自上而下的聚类方法构建出了空间复杂度为$O(n)$的索引结构，并称之为HCTree。依据HCTree，本章还设计了一种时间复杂度约为$O(\log(n))$的检索方式以及索引结构的更新方法。此外，本章还提出了一种基于历史查询的索引优化算法，即通过历史查询及其结果都被用来提升索引结构的性能，并将优化后的索引结构称为d-HCTree。

本章主要贡献如下：
\begin{itemize}
    \item 本章为高维空间中的$k$近邻问题设计了一个简单高效的索引结构，称为HCTree，空间复杂度为$O(n)$，其中$n$是数据规模的大小。
    \item 本章设计了一种高效的检索方法，在HCTree或d-HCTree中检索$k$近邻的时间复杂度为$O(\log(n)+b)$，其中在候选集中验证$k$近邻的时间为$O(b)$。$b$是HCTree中数据块大小的阈值，与$k$呈线性相关。
    \item 本章设计了一种基于历史查询的索引优化算法。通过识别、收集查询结果准确率不佳的查询点，在离线的条件下以扩大搜索范围的方式发现这些查询点更好的结果，并将结果存储在叶子节点中达到提升查询准确率的目的。
    \item 本章用7个真实的数据集对本章提出的$k$近邻查询技术的性能进行全面的评估，通过与当前最先进的$k$近邻查询技术的对比表明了本章提出方法的有效性，其中d-HCTree在查询精度和查询效率上显著优于其他方法
\end{itemize}

本章的组织结构如下：首先在3.2节对$k$近邻查询问题进行了形式化的定义，之后在3.3节中详细的描述了HCTree索引结构的构建过程，并分析了索引结构构建过程的时间复杂度以及索引结构的空间复杂度；在3.4节中主要描述了用于HCTree索引结构的更新和查询方式，提出了一种时间复杂度约为$O{\log(n)}$的查询方式，并设计了索引结构的更新方法；在3.5节提出了一种基于历史查询的索引优化算法，并将优化后的索引结构命名为d-HCTree；最后通过实验验证了索引结构参数选择的依据。实验表明d-HCTree与当前$k$近邻查询技术相比具有查询时间短、索引空间小、查询结果准确的特点。

\subsection{问题描述}
本节将详细的描述$k$近邻查询问题，表~\ref{tab:notation}总结了本章经常使用的符号，其中$\mathbb{R}^d$表示维度或是特征数量为$d$的特征空间。
\begin{table}[h]\small
\setstretch{1.5}
\centering
\bicaption{符号总结}{Summary of Notations}
\begin{tabular}{c l}
  \toprule
  \textbf{符号}       & \textbf{定义} \\ \hline
  $\mathcal{D}$           & 空间$\mathbb{R}^d$下的数据集\\
  $n$                     & 数据集大小\\
  $d$                     & 维度\\
  $q$                     & $\mathbb{R}^d$中的一个查询\\
  $R^*(q)$                & $q$的真实$k$NN结果\\
  $R(q)$                  & $q$的近似$k$NN结果\\
  $u$                     & HCTree的一个叶子结点\\
  $leaf(q)$               & 查询$q$检索到的叶子结点\\
  \bottomrule
\end{tabular}
\label{tab:notation}
\end{table}

% \begin{table}[h]\small
% \setstretch{1.5}
% \centering
% \bicaption{符号总结}{Summary of Notations}
% \begin{tabular}{c l| c l}
%   \hline
%   \textbf{符号}         & \textbf{定义}                         &\textbf{符号}          & \textbf{定义}\\ \hline
%   $\mathcal{D}$         & 空间$\mathbb{R}^d$下的数据集          & $R^*(q)$              & $q$的真实$k$NN结果\\
%   $n$                   & 数据集大小                            &$R(q)$                 & $q$的近似$k$NN结果\\
%   $d$                   & 维度                                  &$u$                    & HCTree的一个叶子结点\\
%   $q$                   & $\mathbb{R}^d$中的一个查询            &$leaf(q)$              & 查询$q$检索到的叶子结点\\
%   \hline
% \end{tabular}
% \label{tab:notation}
% \end{table}

\subsubsection{问题定义}
$\mathbb{R}^d$表示$d$维特征空间，$\mathcal{D}$代表在特征空间$\mathbb{R}^d$中的$N$个样本点的集合，$||\cdot,\cdot||$代表着特征空间空间$\mathbb{R}^d$内的距离度量。在不同的应用场景中，距离度量可以是任意距离函数。基于特征空间空间$\mathbb{R}^d$、数据集$\mathcal{D}$以及距离函数$||\cdot,\cdot||$对$k$近邻查询的定义如下：
\begin{mydef}
\textbf{$k$近邻查询：}给定一个数据集$\mathcal{D}$和一个查询$q\in\mathbb{R}^d$，$k$近邻查询就是检索$\mathcal{D}$到$q$中最近的$k$个数据点，用$R^*(q)$表示。则$\forall x\in\mathcal{D}$且$x\notin R^*(q)$，且满足$p_i \in R^*(q)(1\leq i\leq k)$都有$||q, x|| > ||q, p_i||$。
\end{mydef}

\begin{table}[htb]\small
\setstretch{1.5}
\centering
\bicaption{$k$NN搜索的例子}{Example of $k$NN Search}
\begin{tabular}{c cccc}
  \toprule
                            & \boldmath{$o_1$}    & \boldmath{$o_2$}    & \boldmath{$o_3$}    &    \boldmath{$o_4$}\\ 
 \hline
 \boldmath{$o_i$}           &  $(1, 1)$           &  $(2, 2)$           &  $(1, 0)$           &  $(6, 1)$\\ 
 \boldmath{$\|o_i, q\|^2$}  & 2                   & 8                   & 1                   & 37       \\ 
 \bottomrule
\end{tabular}
\label{tab:examplekNN}
\end{table}

例如，表~\ref{tab:examplekNN}所示，在二维欧几里得空间内，数据集$\mathcal{D}$中共包含四个点$o_1-o_4$，若查询点$q=(0,0)$，则对于查询点$q$来说，$k=3$时得到的查询结果应该是$[o_3,o_1,o_2]$。接下来介绍两个用于评估$k$近邻查询结果精度的评价指标。

\textbf{总体比例（overall~ratio）：}设查询点$q$到$\mathcal{D}$中的$k$近邻的距离记为$O^*_j$($1\leq j \leq k$)，通过$k$近邻查询技术得到的查询点$q$到$k$个近邻的距离记为$O_j$($1\leq j \leq k$)，则总体比例（overall~ratio）如式\ref{eq:ratio}所示：
\begin{equation}
\label{eq:ratio}
\textsf{overall ratio} = \frac{1}{k}\sum^{k}_{j=1}\frac{\|q,o_j\|}{\|q,o^*_j\|}~~~\textsf{overall~ratio}\geq1
\end{equation}

\textbf{召回率（recall）：}设查询点$q$在数据集$\mathcal{D}$中的$k$近邻记为$R^*(q)$，通过$k$近邻查询技术得到的查询点$q$到$k$近邻记为$R(q)$，则召回率（recall）如式~\ref{eq:recall}所示。
\begin{equation}
\label{eq:recall}
\textsf{recall}=\frac{|R^*(q)|\cap|R^(q)|}{|R^*(q)|}~~~\textsf{recall}\leq1
\end{equation}
其中$|\cdot|$表示集合中的元素数量

\subsection{HCTree构建}
本节提出了一种聚类算法称之为边缘聚类算法，如算法~\ref{alg:marginMeans}所示。本基于边缘聚类算法以自上而下的形式构建出用于支持$k$近邻查询的索引结构这里称之为HCTree。本节将从：1）边缘均值聚类；2）索引构建；3）复杂度分析，这三部分描述HCTree的构建过程。

\subsubsection{边缘均值聚类算法}
传统的K-means算法可以将数据集划分成指定的$K$个簇，并且有着同一簇内数据点的相似性高，不同簇间数据点相似性低的特点，因此在同一簇内的数据点很有可能互为彼此的$k$近邻。然而传统的K-means算法的表现受到参数$K$和起始中心点的影响极大，为了保证构建索引的稳定性和高效性，本文提出了边缘均值聚类算法。

边缘均值聚类算法，是从数据集中选择偏离数据集中心最远的两个数据点作为中心点，将数据集划分成两个簇。解决了传统K-means算法迭代次数多，容易陷入局部最优解，多次聚类结果不一致等问题。
\begin{algorithm}[H]
\setstretch{1.5}
\caption{边缘均值聚类} 
\label{alg:marginMeans}
\begin{algorithmic}[1]
\REQUIRE 样本空间 $\mathcal{D} = \{p_1, p_2, \dots, p_n\}$, 最大迭代次数 $I_{max}$
\ENSURE 簇划分 $C = \{C_1,C_2\}$
\STATE 计算样本空间 $\mathcal{D}$ 的中心点 $center\_point = \frac{1}{|\mathcal{D}|}\sum_{p \in \mathcal{D}}p$

\STATE 计算$center\_point$ 与数据点 $p_i(1\leq i\leq n)$的距离:$d_i = ||p_i, center\_point||$
\STATE 选择距离 $center\_point$ 最远的数据点标记 $\lambda_i = argmax_{i \in \{1, 2, \dots, n\}d_{i}}$
\STATE 得到一个聚类中心点 $\mu_1 = p_{\lambda_i}$

\STATE 计算 $\mu_1$ 与数据点 $p_i(1 \leq i \leq n)$ 的距离:$d_i = ||p_i, \mu_1||$
\STATE 选择距离 $\mu_1$ 最远的数据点标记 $\lambda_i = argmax_{i \in \{1, 2, \dots, n\}d_{i}}$
\STATE 得到另外的聚类中心点 $\mu_2 = p_{\lambda_i}$
\STATE 选择 $\{ \mu_1, \mu_2\}$作为初始均值向量

\WHILE{$flag \leq I_{max}$ and 当前均值向量均为更改}
    \FOR{$j=1, 2, \dots, m$}
        \STATE 计算数据点 $p_j$与各均值向量 $\mu_i(1 \leq i \leq k)$ 的距离:$d_{ji} = ||p_i, \mu_j||$
        \STATE 根据距离最近的均值向量确定$p_j$的簇标记 $\lambda_j = argmin_{i \in \{1, 2, \dots\}d_{ji}}$
        \STATE 将样本 $p_j$ 划入相应的簇 $C_{\lambda_i} = C_{\lambda_i} \cup \{p_i\}$
    \ENDFOR
    
    \FOR{$i=1, 2, \dots, k$}
        \STATE 计算新的均值向量 $\mu_i' = \frac{1}{|C_i|}\sum_{p \in C_i}p$
        \IF{$\mu_i' \neq \mu_i$}
            \STATE 将当前均值向量 $\mu_i$ 更新为 $\mu_i'$
        \ELSE
            \STATE 保持当前均值向量不变
        \ENDIF
    \ENDFOR
    \STATE $flag \leftarrow flag + 1$
\ENDWHILE
\end{algorithmic}
\end{algorithm}

以欧式空间为例，边缘均值聚类如算法~\ref{alg:marginMeans}所示。首先计算出数据集的中心点记为$center\_point$（第1行），选择数据集中距离中心点$center\_point$最远的数据点$\mu_1$（第2-4行），选择距离$\mu_1$最远的数据点$\mu_2$（第5-7行），将$\mu_1$、$\mu_2$作为起始中心点开始聚类（第8行）。分别计算数据集内数据点与簇中心$\mu_1$、$\mu_2$的距离，找出离数据点最近的簇中心$\mu_i$，并将数据点分配给簇中心$\mu_i$所对应的簇中（第10-14行），然后计算簇中数据点的特征均值作为新的聚类中（第15-16行）。迭代这个过程，直到聚类中心不再变化或是超过了最大迭代次数停止迭代(第17-23行)。

\subsubsection{索引构建}
HCTree索引结构以自上而下的方式，采用边缘均值聚类算法划分数据集$\mathcal{D}$构建索引结构。如图~\ref{fig:hctree}所示，HCTree中的每个节点都含有一个质心，从逻辑上代表着其子树所包含的所有数据点。此外，索引中的每个内部节点都有两个分支，每个叶节点都有一个数据块，在数据块中包含着一个簇的数据点。

\begin{figure}[h]
\centering
\includegraphics[width=0.7\linewidth]{Thesis/content/FIG/Three/three_hcTree.png}
\bicaption{HCTree树}{Example of HCTree}
\label{fig:hctree}
\end{figure}

算法~\ref{alg:HcTree_Construction1}详细的描述了HCTree的构建过程。初始时，所有的数据点都在一个簇中，作为HCTree的根节点。第6行到第12行是划分簇的过程，在迭代的过程中，通过边缘均值聚类算法，将一个簇划分成两个簇。这里值得一提的是，对于每个数据点，我们计算数据点和簇内中心点、簇内数据点的距离和，并将数据点分配给距离和最小的簇。一旦簇的大小不超过阈值$b$，将不再继续分裂（第1-2行），通过阈值$b$限制了数据块的容量，保证了叶子结点包含的数据的点的数量不大于$b$。
\begin{algorithm}[h]
\setstretch{1.5}
\caption{构建HCTree($\mathcal{D}$, $b$, $I_{max}$)} \label{alg:HcTree_Construction1}
\begin{algorithmic}[1]
\REQUIRE 数据集$\mathcal{D}$, 块的最大尺寸 $b$, 最大迭代次数 $I_{max}$,
\ENSURE HCTree $T$
\IF{$|\mathcal{D}|< b$}
	\STATE 对数据集$\mathcal{D}$中的点构建叶子节点;
\ELSE
	\STATE $P\leftarrow$ 依据边缘均值距离算法从$\mathcal{D}$中选取2个点作为质心;
	\STATE $iterations \leftarrow 0$
	\WHILE{$iterations < I_{max}$}
		\STATE $C\leftarrow$ 将$\mathcal{D}$中的点聚集在其最近的中心$P$周围；
		\STATE $P_{new}\leftarrow$ 簇$C$中点的均值;
		\IF{$P = P_{new}$}
			\STATE break;
		\ENDIF
		\STATE $P\leftarrow P_{new}$;
		\STATE $iterations\leftarrow iterations +1$;
	\ENDWHILE
	\FOR{each cluster $C_i\in C$}
		\STATE 创建质心为$P_i$的非叶节点;
		\STATE 构建HCTree($C_i,b,I_{max}$);
	\ENDFOR
\ENDIF
\end{algorithmic}
\end{algorithm}

这里涉及到了一个超参数$b$，$b$表示叶子节点中数据块的大小，这里将其定义为$b = \mu k$，其中$k$是查询近邻的数量，$\mu$是一个大于1的整数。随着$\mu$的增加，索引结构的查询精度也会随之提高，但查询时间也相应增加，因此通过实验证明，$\mu=3$是最为合适的选择，它可以实现较高的搜索精度的同时，降低查询时间的开销。

以自上而下的方式对数据集进行划分，构建索引结构，相较于自下而上的划分方式而言：1）效率更高：自下而上的划分方式构建索引结构的时间复杂度至少$O(n^2)$，而采用自上而下的划分方式时间复杂度为$O(n\log(n))$；2）更准确：与自下而上的划分方式构建索引结构相比，自上而下的划分方式在顶部做划分时，可以考虑到全局信息~\cite{2010Introduction}，降低离群点对划分的影响。

\subsubsection{复杂度分析}
索引构建的时间复杂度，空间复杂度直接影响着索引是否具备实用价值，这里对索引构建过程中的时间、空间复杂度进行分析说明。

\textbf{时间复杂度：}在HCTree的构建过程中，需要对索引结构中的每个节点执行边缘均值聚类算法（算法~\ref{alg:HcTree_Construction1}中的第5-12行），若节点$v$中在逻辑上所包含的数据点为$n_v$，则聚类过程产生的时间复杂度可以记为$O(I_{max}n_v)$。对于索引结构的任意一层来说都满足$\sum n_v = n$，所以对于索引结构在每一层产生的时间复杂度可以记为$O(I_{max}n)$。假设索引结构是一个平衡二叉树，则索引结构共有$\log (n)$层，因而整个索引的构建过程的时间复杂度为$O(I_{max}n\log (n))$。

其中$I_{max}$是聚类算法中，簇中心点的最大迭代次数，选择合适的$I_{max}$不仅关系着索引构建的时间复杂度，也直接影响着索引结构的性能。执行较少的迭代次数可以极大的减少索引构建的时间，但会导致索引结构的性能下降。为了选择合适的$I_{max}$，本文通过实验验证了当$I_{max}=15$时索引结构的性能类似于持续聚类迭代直至收敛的索引结构的性能。

\textbf{空间复杂度：}假设HCTree中的节点数量为$|T|$，则索引结构总的空间复杂度为$O(|T|)$。因此节点数量直接关系影响着索引结构的空间复杂度，当索引结构是一棵二叉平衡树时，树的高度为$\log(n)$，节点数量最少，空间复杂度为$O(n)$。而在最坏的情况下，树的高度为$n$，则空间复杂度为$O(n^2)$。为了更准确的描述HCTree的空间复杂度，本文通过实验证实了，在7个真实数据集上构建的HCTree索引近似平衡，因此HCTree的空间复杂度为$O(n)$

\subsection{查询和更新}
在这一小节中，提出一种贪婪的搜索方式以实现高效的查找。此外，本节将详细的描述索引结构的更新过程。

\subsubsection{数据检索}
这里将详细的说明通过HCTree进行高效的$k$近邻查询处理。通常来说，$k$近邻查询可以分成两个阶段：1)检索候选集；2)通过计算查询点到候选集的距离确定$k$近邻。为了取得最佳的检索时间效率，需要最快的确定检索的候选集，以及让候选集的规模尽可能的小。

利用HCTree，我们提出了一种高效的贪婪搜索策略。算法~\ref{alg:HcTree_searching}详细的说明了这个过程。给定一个查询数据点$q$，从根节点开始检索（第1行），给定一个扩展的节点$N$，对于$N$的每个子节点，计算到查询数据点$q$的距离，选择质心最接近$q$的子节点为扩展的节点$N$（第4行），在下一次迭代中展开，直至节点$N$是HCTree的叶子节点，循环终止。（第2-4行）。存储在该叶节点中的所有数据点作为$q$（第5行）的候选集。

\begin{algorithm}
\setstretch{1.5}
\caption{搜索HCTree}
\label{alg:HcTree_searching}
\begin{algorithmic}[1]
\REQUIRE HCTree $T$, 查询点$q$, 最近邻数$k$
\ENSURE 候选集合
\STATE $N\leftarrow$ $T$的根节点
\WHILE {$N$ 不是叶子结点}
	\STATE $C \leftarrow$ $N$的孩子结点
	\STATE $N \leftarrow$ 中心点距离$q$最近的结点$C$
\ENDWHILE
\RETURN $N$中的数据点
\end{algorithmic}
\end{algorithm}

如图~\ref{fig:greedySearchHctree}所示的索引结构中，检索数据点$q=(1,1)$的候选集的过程如下：从根节点$u_0$开始，计算$u_0$的两个子节点$u_1$和$u_2$到查询点$q$的距离，由于$u_2$的质心更接近$q$，选择$u_2$作为新的扩展点，分别计算$u_2$的两个子节点$u_5$ 和$u_6$到查询点$q$的距离，同理，选择$u_5$作为新的扩展点，如此循环下去，直至循环至扩展点为叶子节点$u_7$时停止，输出它的数据块，$\{v_8, v_9, v_{10}\}$作为查询点$q$的$k$近邻的候选集。

\begin{figure}[h]
\centering
\includegraphics[width=0.7\linewidth]{Thesis/content/FIG/Three/three_greedySearch.png}
\bicaption{贪婪搜索}{Greedy Search}
\label{fig:greedySearchHctree}
\end{figure}

\textbf{时间复杂度：}如算法~\ref{alg:HcTree_searching}所示，查询的时间复杂度是$O(2h)$，2是每个内部节点的分支数目，$h$是树的高度。计算查询点与候选集中各数据点距离的时间复杂度为$O(b)$，因此综合时间成本可以记为$O(2h+b)$。鉴于HCTree的树高大约为$\log(n)$，$b=\mu k$是一个较小的常数，因此查询的时间复杂度为$O(\log(n))$。

\subsubsection{索引更新}
索引的更新可以归结为插入数据，删除数据，因为删除数据可以通过将数据标记为“已删除”，将被标注的数据从查询结果中剔除，简单高效的实现了数据的“删除”，因此这里主要说明索引结构如何插入数据。

在HCTree中插入新的数据点需要的计算量非常小：仅需要将新的数据点添加到通过贪婪搜索算法检索到到叶子节点中的数据块中。因此，当新的数据点的插入时不需要重新构建HCTree。由于任意叶子节点数据块的大小都必须满足$b\leq\mu k$，因此一旦一个叶子节点的数据块超出了指定的大小，就需要将数据块中的一些数据点重新分配到其他叶子节点的数据块中。然而，替换策略是多样的，因此最佳的替换策略应该充分的考虑工作负载的分布。例如，搜索引擎中的查询往往符合齐普夫定律（Zipf~law）。因此，在齐普夫分布下的查询可以选择最近最少使用策略（LFU），即选择在叶子节点中作为$k$近邻出现频率最低的数据点重新分配到其他叶子节点的数据块中。记将要被重新分配的数据点为$v$，找到距离点$v$最近的数据块未满的叶子节点，将其添加到数据块中。通过这种更新方式可以有效的使索引结构适应查询的工作负载分布。

\subsection{基于历史查询的索引优化算法}
HCTree在时间复杂度和空间复杂度上有着出色的性能表现，但其精度相对较低。究其原因我们发现它仍是一个静态方法，不能从查询中学习，面对反复出现的查询点，总是返回相同的查询结果。一个好的索引应该从历史查询中吸取教训，逐步改进查询结果，以提高查询性能。为此，本节提出了基于历史查询的索引优化算法，并将之应用于HCTree，优化后的索引结构称为d-HCTree。

要从错误中学习就需要：1)错误检测，即识别出通过HCTree得到的哪些$k$近邻的结果是不准确的；2)错误修复，即为这些查询点发现更准确的结果；3)索引优化，即将更准确的结果存储到检索到的叶节点中。

\subsubsection{错误检测}
在欧式空间中，距离查询点越远表明相似度越低，因此我们可以通过设置阈值来检查错误的查询结果。若存在查询点$q$，通过HCTree检索得到得$K$近邻记为$R(q)$，则$\|q,R(q)\|$为查询点$q$到$R(q)$中各个数据点距离得平均值，即$\|q, R(q)\| = \frac{1}{|R(q)|}\sum_{v\in R(q)}\|q, v\|$。

设置距离阈值为$\theta$，如果$\|q,R(q)\|<\theta$，则认为$R(q)$的误差在可接受的范围内，无需扩大查询范围，反之，查询点$q$将被添加到队列$L$中，准备对$q$扩大搜索范围。尽管设置距离阈值可以起到错误检测的作用，但由于$\theta$的取值范围极大，选择一个合适的值是非常困难的。为了解决这个问题，本文通过累积分布函数将距离阈值取值范围缩小至$[0,1]$。对查询$q$来说，$R^*(q)$是$q$在样本空间中精确的$k$近邻结果，则有关$k$近邻平均距离的累计分布函数被定义为，
\begin{equation}
\label{eq:theta}
\Psi(\theta) = \Pr[\|q, R^*(q)\|\geq \theta]
\end{equation}

即在给定累计分布函数$\Psi(\cdot)$和距离$d$的情况下，$\Psi(d)$表示查询点$q$到$k$近邻的平均距离大于$d$的概率，通过$\Psi(d)$可以得到$\Psi(\cdot)$的反函数，记为$\Psi^{-1}(\cdot)$。则$\Psi^{-1}(\epsilon)$表示的含义为，查询数据点有$\epsilon$的概率需要扩大搜索范围。显然，$\epsilon$的选择需要权衡查询的准确率和查询时间，$\epsilon$越小，检测到的错误结果就越少，索引更新的成本就越低。为了避免冷启动的问题，$\epsilon$在开始时的值应该设置成很大的（趋于1），随着索引结构的优化，精度的增益显著变小时，可以降低$\epsilon$值来降低优化开销。

\begin{algorithm}
\setstretch{1.5}
\caption{束搜索($T$, $q$, $c$)} \label{alg:BeamSearch}
\begin{algorithmic}[1]
\REQUIRE HCTree+ $T$, 查询点$q$, 束范围$c$
\ENSURE 候选集$R$ 
\STATE $N\leftarrow$ $T$的根结点;
\IF {$N$ 不是叶子结点}
	\STATE $C \leftarrow$ $N$的孩子结点;
	\STATE $N \leftarrow$ $c$个中心点距离$q$最近的结点$C$;
	\FOR{each node $v$ in $N$}
	   \IF {$v$ 不是叶子节点} 
	        \STATE 束搜索($v$, $q$, $c$);
	   \ELSE
	        \STATE 输出$v$中的数据点;
	   \ENDIF
	\ENDFOR
\ELSE
    \STATE 输出$v$中的数据点;
\ENDIF
\end{algorithmic}
\end{algorithm}

\subsubsection{错误修复}
由上节的错误检测得到了一个$k$近邻结果误差较大的查询点列表$L$，为了提高列表$L$中查询点$q$的精度，需要扩大在HCTree上的搜索范围。尽管最理想的情况是通过遍历整个样本空间获得查询点$q$准确的$k$近邻，但这样做的代价是昂贵的，在时间上是不可行的，因此本文提出了束搜索，伪代码如算法~\ref{alg:BeamSearch}所示。通过束搜索可以灵活的选择搜索范围，从而在搜索时间，搜索精度上取得平衡。具体来说，给定一个搜索范围$c$、查询数据点$q$，初始化扩展列表$N$（第三行），计算列表$N$中所有节点的子节点到查询数据点$q$的距离，选择质心最近的$c$个子节点组成扩展列表$N$（第4行），在下一次迭代中展开，直至列表$N$中全是HCTree的叶子节点，循环终止（第5-9行）。显然，如果$c=1$，束搜索就变成了贪婪搜索，而如果$c=\infty$，束搜索变成穷举搜索。因此，算法~\ref{alg:BeamSearch}的时间复杂度为$O(ch)$。

具体来说，例如在如图~\ref{fig:beamSearchHctree}所示的索引结构中$c=2$，检索数据点$q=(1,1)$的候选集的选择过程如下：从根节点$u_0$开始，选择$u_0$的两个子节点$u_1$和$u_2$作为扩展点，分别计算$q$到$\{u_3,u_4,u_5,u_6\}$的距离，由于$\{u_5,u_6\}$的质心更接近查询点$q$，但此时$u_6$已经是叶子节点，不可扩展。因此再选择$u_5$作为扩展点，分别计算$u_7$和$u_8$的质心，由于$u_7$的质心更接近$q$，将$u_7$也作为结果的一部分。此时查询完成，查询点$q$的检索结果为$u_5 \cup u_7=\{u_8,u_9,u_{10},u_{15},u_{16},u_{17},u_{18},\}$做为查询点$q$的候选集。

\begin{figure}[h]
\centering
\includegraphics[width=0.7\linewidth]{Thesis/content/FIG/Three/three_beamSearch.png}
\bicaption{束搜索 $c$=2}{Beam search with $c$=2}
\label{fig:beamSearchHctree}
\end{figure}

\subsubsection{索引优化}
设$u$为查询为查询点$q$通过索引结构检索到的叶子节点，$R(q)$是通过贪婪搜索得到的近似$k$近邻的结果。$R'(q)$是通过束搜索得到的接近最优的近似$K$近邻结果。为了存储新发现的结果，d-HCTree为叶子节点$u$增加了冗余块。查询点$q$对d-HCTree的优化需要将$R'(q)\backslash R(q)$添加到叶子节点$u$的冗余块中，当叶子节点$u$再次被检索到的时候，冗余块和$R(q)$共同组成了新的$k$近邻候选集返回。

此外，为了避免增加查询的时间复杂度，叶子节点增加的冗余块应当有所限制，不应该无限的增长下去，d-HCTree将数据块的大小限定在了$[0,b]$之间。一旦一个冗余块被填满了，有新的结果需要被插入冗余块，需要从冗余块中丢弃一些数据点，鉴于本文实验中查询的分布遵循齐夫定律因此本文采用了LFU策略，剔除作为$k$近邻出现次数最少的数据点。

\subsection{实验结果与分析}
本节将通过在7个公开的数据集上验证本章提出的索引结构HCTree，以及基于历史查询的索引优化算法的有效性，经过优化的索引结构记为d-HCTree。

\subsubsection{实验设置}
\textbf{对比算法：}本节将实现之前提出的算法HCTree，作为近似$k$近邻索引结构，并基于HCTree实现了d-HCTree。本章将对比HCTree、d-HCTree以及另外四种当前最优的近似最近邻搜索算法进行比较（1）SRS~\cite{DBLP:journals/pvldb/SunWQZL14}是一种最先进的基于LSH的算法，该算法使用r树来索引投影空间中的点。（2）HD-Index~\cite{DBLP:journals/pvldb/AroraSK018}是最近提出的一种基于层次结构人工神经网络算法，称为rdb-树。（3）Flann~\cite{A:flann}是一个著名的基于随机kd树的近似最近邻搜索算法。（4）oasis~\cite{DBLP:conf/sigmod/ZhangCYMR20}是一项基于LSH指数的最新研究，它使用距离度量学习策略来持续提高准确性和效率。本文使用了由~\cite{DBLP:journals/pvldb/SunWQZL14,DBLP:journals/pvldb/AroraSK018,A:flann,DBLP:conf/sigmod/ZhangCYMR20}的作者提供的源代码。

\textbf{参数设置：}默认情况下，我们设置了最近邻的数量$K=10$。算法的参数设置如下：HCTree，d-HCTree：数据块容纳数据上限$b=30$，最大迭代次数$I_{max}=15$,束搜索$c=500$，$\epsilon = 1$（为了避免冷启动）。根据SRS，HD-Index，Flann，oasis作者的建议设置对比算法的参数。SRS：近似比$c=1.2$,随机投影${mSRS} = 6$；HD-index：(a)sift数据集：${tabSize} = 4$，${leafOrder} = 48$，${lnumber}=4$；(b)audio和nuswide，${tabSize}=8$，${leafOrder} = 34$，${lnumber} = 3$；(c)notre，$tabSize=4$, $leafOrder=21$，$lnumber=3$；(d)其他的数据集$tabSize=16$，$leafOrder=21$，$lnumber=3$；（4）Flann：KD-Tree的数量$kd=4$，${search\_checks}=128$。

\textbf{数据集和数据分布：}本文共使用了7个公开的数据集并对去掉了数据集中的重复向量~\cite{DBLP:journals/pvldb/AroraSK018,DBLP:journals/pvldb/ZhengZWHLJ20}。表~\ref{tab:data}报告了数据集和查询工作负载的相关信息。它们均使用于欧几里得空间，但维度（$d$）和数据集大小（$n$）各不相同。我们根据~\cite{2013Hadoop}生成查询的工作负载。具体来说，在所有查询中，只有少数数据集比其他数据集使用更频繁，而剩下的长尾数据集只是偶尔被访问。我们为每个数据集生成了一批参数$\alpha=2$的符合Zipf定律的数据分布的查询数据和测试数据。
\begin{table}[htb]\small
\setstretch{1.5}
\centering
\bicaption{数据集和查询工作负载}{Datasets and Query Workloads}
\begin{tabular}{c c c c c c}
  \hline
 \textbf{Abbr.} & \textbf{数据集} & \textbf{数据量 }\boldmath{$n$}  & \textbf{维度} \boldmath{$d$} & \textbf{\# 训练集} & \textbf{\# 测试集}\\ \hline
\textbf{A} & audio\footnote{\url{http://cs.princeton.edu/cass/audio.tar.gz}}         & 53,387 & 192  & 42,709 & 1000\\
\textbf{B} & sun\footnote{\url{https://groups.csail.mit.edu/vision/datasets/ADE20K/}}           & 79,106 & 512  &63,284 & 1000\\
\textbf{C} & enron\footnote{\url{http://www.cs.cmu.edu/enron/}}         & 94,987 & 1,369 &75,989 &1000 \\
\textbf{D} & trevi\footnote{\url{http://phototour.cs.washington.edu/patches/default.htm}}    & 99,900 &4,096 & 79,920 & 1000 \\
\textbf{E} & nuswide\footnote{\url{http://cs-people.bu.edu/hekun/data/TALR/NUSWIDE.zip}}      & 268,643 & 500  &214,914 &1000\\
\textbf{F} & notre\footnote{\url{http://phototour.cs.washington.edu/datasets/}}         & 332,668 & 128 &266,134 &1000\\
\textbf{G} & sift\footnote{\url{http://corpus-texmex.irisa.fr/}}          & 994,461 & 128 &795,568 &1000\\
  \hline
\end{tabular}
\label{tab:data}
\end{table}

\textbf{audio：}数据集包含了约5万条通过美国国防部高级研究计划局（DARPA~TIMIT）提供的Marsyas库的音频速度数据集中提取的192维音频特征向量。

\textbf{sun：}数据集中包含了约8万条从图片中以基于内容（Context~of~a~Scene，GIST）的方式抽取的512维的特征向量。

\textbf{enron：}数据集来源于电子邮件，由 Yifang等人提取形成了约10万条1369维的特征向量。 

\textbf{trevi：}数据集由40万个1024位图(bmp)图像组成，每幅图像包含一个$16\times16$的图像块阵列。通过大小为$16\times16$的标准尺度和方向进行灰度采样，构成了大约10万条4096维向量。  
\textbf{nuswide：} 数据集由27万张网络图片构成，每一张图片都用一个500维的词袋矢量来表示

\textbf{notre：}数据集包含了大约30万张128维的图片及其重建图片。  

\textbf{sift：}数据集包含了大约1百万个通过SIFT方法抽取的128维的特征向量。  

\textbf{评估指标：}本章主要考量以下三个指标：（1）准确性：我们采用总体比例（overall~ratio）和召回率（recall）来评估所有方法的准确性；（2）时间效率：我们使用查询的平均查询时间来评估各方法的时间效率；（3）索引大小：我们使用索引空间的大小来评估各个方法的空间开销。

\textbf{实验环境：}所有的实验都是在一台拥有2.6GHz、4核AMD处理器和16GB内存、运行在Linux~Ubuntu20.4的PC上进行测试的。我们的算法完全在主存中运行。

\subsubsection{参数选择}
在本节中，将分析在HCTree和d-HCTree中设置不同的参数在性能上的影响，鉴于篇幅原因，我们只呈现audio和sun这两个数据集的结果，在其他的数据集上也观察到了类似的趋势。

\begin{figure}[htb]
	\centering
\subfigure[]{
\label{fig:SizeTime}
\includegraphics[width=0.3\linewidth]{Thesis/content/FIG/Three/BeamTime.eps}
}
\subfigure[]{
\label{fig:Sizerecall}
\includegraphics[width=0.3\linewidth]{Thesis/content/FIG/Three/BeamRecall.eps}
}
\subfigure[]{
\label{fig:Sizeratio}
\includegraphics[width=0.3\linewidth]{Thesis/content/FIG/Three/BeamRatio.eps}
}
\bicaption{效率与可扩展性}{Efficiency and Scalability}\label{fig:Beam}
\end{figure}

\begin{figure}[htb]
	\centering
\subfigure[]{
\label{fig:BlksizeTime}
\includegraphics[width=0.3\linewidth]{Thesis/content/FIG/Three/GraBlksizeTime.eps}
}
\subfigure[]{
\label{fig:BlksizeRecall}
\includegraphics[width=0.3\linewidth]{Thesis/content/FIG/Three/GraBlksizeRecall.eps}
}
\subfigure[]{
\label{fig:BlksizeRatio}
\includegraphics[width=0.3\linewidth]{Thesis/content/FIG/Three/GraBlksizeRatio.eps}
}
\subfigure[]{
\label{fig:dKQuerytime}
\includegraphics[width=0.3\linewidth]{Thesis/content/FIG/Three/GradKQuerytime.eps}
}
\subfigure[]{
\label{fig:dKRecall}
\includegraphics[width=0.3\linewidth]{Thesis/content/FIG/Three/GradKRecall.eps}
}
\subfigure[]{
\label{fig:dKRatio}
\includegraphics[width=0.3\linewidth]{Thesis/content/FIG/Three/GradKRatio.eps}
}
\bicaption{数据块大小与$k$值对效率的影响}{Effect of Block size and $k$}\label{fig:para}
\end{figure}

\textbf{束搜索范围的选择：}在这组实验中（如图~\ref{fig:Beam}），本文通过改变束搜索范围的大小评估模型的性能。如\tupian{fig:SizeTime}所示，展示了搜索范围与搜索时间之间的关系。结果表明，搜索时间随搜索范围的增加呈线性增长，这与本文的分析结果一致。\tupian{fig:Sizerecall}-\tupian{fig:Sizeratio}，展示了搜索范围与准确率之间的关系。结果表明，扩大搜索范围可以明显的提高查询的准确率，当搜索范围$c=300$时，d-HCTree总能获得一个近乎最优的精度。

\textbf{数据块大小的选择和$k$的选择：}从\tupian{fig:BlksizeTime}可以看出，d-HCTree的效率对不同的$b$值并不那么敏感。当$b$较小时，搜索时间存在一定的差异。随着$b$的增加，敏感度降低。\tupian{fig:BlksizeRecall}-\tupian{fig:BlksizeRatio}说明当块尺寸较小时，增加$b$可以提高精度。与此同时，d-HCTree对于较小的块，例如$b =2k$，就可以得到相当好性能。从\tupian{fig:dKQuerytime}可以看出，查询时间近似于$k$成线性关系增长。从\tupian{fig:dKRecall}-\tupian{fig:dKRatio}可以看出，d-HCTree的精度对不同的$k$值并不那么敏感。在不同的$k$值下，d-HCTree获得了相似的精度。

\begin{figure}[ht]
	\centering
\subfigure[]{
\label{fig:OptQTime}
\includegraphics[width=0.43\linewidth]{Thesis/content/FIG/Three/GraOptQTime.eps}
}
\subfigure[]{
\label{fig:OptRecall}
\includegraphics[width=0.43\linewidth]{Thesis/content/FIG/Three/GraOptRecall.eps}
}
\subfigure[]{
\label{fig:OptRatio}
\includegraphics[width=0.43\linewidth]{Thesis/content/FIG/Three/GraOptRatio.eps}
}
\subfigure[]{
\label{fig:OptSize}
\includegraphics[width=0.43\linewidth]{Thesis/content/FIG/Three/GraOptSize.eps}
}
\bicaption{Effect of Optimizations}{优化算法的有效性}\label{fig:compare}
\end{figure}

\vspace{-8mm}
\subsubsection{优化对比}
为了验证我们的方法的有效性，我们在所有的数据集上展示了基本索引(HCTree)与优化后的d-HCTree的实验结果。从结果来看（图~\ref{fig:compare}），我们可以发现：（1）d-HCTree比HCTree检索速度慢。然而，d-HCTree比HCTree精确8-10倍；（2）d-HCTree索引空间相比于HCTree略大，但最大没有超过5MB（sift数据集）。

\begin{table}[ht]\small
\centering
\zihao{5}
\setstretch{1.5}
\bicaption{Overall Ratio对比}{Comparison of Overall Ratio}
\label{tab:Ratio}
\begin{tabular}{c c c c c c}
\toprule
\textbf{数据集}&\textbf{d-HCTree}&\textbf{SRS}&\textbf{HD-Index}&\textbf{Flann}&\textbf{OASIS}\\  \hline
  {audio}        & 1.0001  & 1.1055  & 1.0000  &1.0231  &1.2342  \\
  {sun}          & 1.00014 & 1.0227  & 1.0000  &1.0936  &1.1233  \\ 
  {enron}        & 1.0005  & 1.0398  & 1.0905  &1.0634  &1.3889   \\ 
  {trevi}        & 1.0050  & 1.0405  & 1.0027  &1.1296  &1.1905   \\
  {nuswide}      & 1.0031  & 1.0463  & 1.1391  &1.0673  &1.1321  \\ 
  {notre}        & 1.0023  & 1.0304  & 1.0214  &1.0929  &1.3294   \\ 
  {sift}         & 1.0025  & 1.0895  & 1.0205  &1.0977  &1.1901   \\ 
\bottomrule
\end{tabular}
\label{tab:compAcc}
\end{table}

\begin{table}[ht]\small
\centering
\setstretch{1.5}
\bicaption{召回率对比}{Comparison of Recall}
\label{tab:recall}
\begin{tabular}{c c c c c c}
  \toprule
\textbf{数据集}&\textbf{d-HCTree}&\textbf{SRS}&\textbf{HD-Index}&\textbf{Flann}&\textbf{OASIS}\\  \hline
  {audio}         &0.999  &0.4515  &1.0000  & 0.6944   & 0.4621    \\ 
  {sun}           &0.9921  &0.5485  &0.9975  & 0.1765   & 0.2722    \\ 
  {enron}         &0.9889  &0.2634  &0.9976  & 0.2274   & 0.2671    \\ 
  {trevi}         &0.97  &0.6554  &0.9849  & 0.3504   & 0.3237    \\
  {nuswide}       &0.7713  &0.2016  &0.6495  & 0.1058   & 0.3355    \\ 
  {notre}         &0.973  &0.7631  &0.7863  & 0.2511   & 0.1233    \\ 
  {sift}          &0.96  &0.2409  &0.7821  & 0.2851   & 0.2048     \\ 
\bottomrule
\end{tabular}
\label{tab:compAcc}
\end{table}

\vspace{-8mm}

\subsubsection{与其他方法对比}
\textbf{查询准确率：}
我们分别从overall ratio和recall两方面比较了准确率。在表~\ref{tab:Ratio}中我们观察到无论数据集维度和大小如何变化，d-HCTree 总是获得很好的 overall ratio(1.00-1.01)，这一点证明了该算法的鲁棒性。表~\ref{tab:recall}展现出所有的数据集上，d-HCTree总是取得最高的准确性。与此同时，我们发现，在高维或大数据集上 (trevi, nuswide, notre 及 sift)，HD-Index 的精度很低。

\textbf{查询时间：}
表~\ref{tab:QueryTime}显示了在实践和理论方面的查询时间比较。结果表明，所有方法的查询处理复杂度都较低，即与$n$线性相关。HD-Index的查询复杂度最低，Flann的查询复杂度最高。然而，这并不意味着HD-Index在时间消耗方面优于Flann。我们观察到，Flann的实际查询效率最高，剩余依次为d-HCTree、SRS、HD-Index和OASIS。具体来说，d-HCTree比SRS快$1-32+$，比HD-Index快至少$80+$，比OASIS快3个数量级。此外，与运行时间随数据大小而快速增长的SRS不同，我们的方法的运行时间随数据集大小而优雅地伸缩，并且随着数据大小的增大而变得越来越高效。注意，我们的方法的一个小缺点是，它的查询时间对维度的数量非常敏感。
% \vspace{-8mm}
\begin{table}[ht]\small
\centering
\zihao{5}
\setstretch{1.5}
\bicaption{查询时间对比}{Comparison of Query Time (ms)}
\label{tab:QueryTime}
\begin{tabular}{c c c c c c}
\toprule
                  & \textbf{d-HCTree}         &                           \textbf{SRS}              &                   \textbf{HD-Index}           &       \textbf{Flann}        &        \textbf{OASIS}                \\ \hline
\multirow{2}*{\textbf{复杂度}}& \multirow{2}*{$O(d\log n)$}& $O(\gamma_2 n)$ & $O(\tau\log n+d)$  & \multirow{2}*{$O(Ld\log n)$}      & $O(\log n+2^mk)$ \\  
                        &                             & $\gamma_2<<1$           & $\tau<<1$  &    & $m<<n$  \\  
  {audio}            & 0.9          & 0.3                                        & 136.1                             & {0.2}              & 353.1                      \\ 
  {sun}              & 1.5            & 4.8                                       & 212.2                             & {0.2}           & 762.8                      \\ 
  {enron}            & 4.5            & 4.8                                        & 441.9                             & {0.4}              & 1609.3                     \\ 
  {trevi}            & 6.6        & 9.8                                        & 864.9                             & {0.8}              & 5398.5                     \\
  {nuswide}          & 2.2         & 20.5                                      & 228.1                             & {0.3}          & 2247.8                     \\ 
  {notre}            & 1.1         & 11.1                                       & 87.0                                 & {0.2}              & 1080.4                     \\ 
  {sift}             & 1.1            & 32.4                                      & 89.3                                 & {0.2}              & 2936.7                     \\ 
  \bottomrule
\end{tabular}
\end{table}

\subsubsection{索引空间}
出于前面提到的同样原因，表~\ref{tab:indexsize}报告了所有数据集上每种方法的索引大小复杂度和实际主存消耗的比较。从实证结果可以看出，HCTree的索引大小最小，而SRS需要的空间消耗最大。我们还观察到，虽然我们的方法的复杂性不是最小的，即与大小($n$)和维数($d$)都是线性的，但索引大小缓慢地随$n$和$d$而变化。

\begin{table}[ht]\small
\centering
\setstretch{1.5}
\bicaption{索引空间对比}{Comparison of Index Size (MB)}
\label{tab:indexsize}
\begin{tabular}{c c c c c c}
\toprule
                  & \textbf{d-HCTree}         &                           \textbf{SRS}              &                  \textbf{HD-Index}           &       \textbf{Flann}        &   \textbf{OASIS}      \\  \hline 
\multirow{2}*{\textbf{复杂度}}& \multirow{2}*{$O(nd)$}&  $O(\gamma_1 n)$ & $O(nd+nm\tau)$ &\multirow{2}*{$O(nd)$} & \multirow{2}*{$O(n)$}      \\  
                         &                       &  $\gamma_1<<1$   &  $m<<n$        &                       &  \\ 
  {audio}            & {7.6}         & 453                                      & 140                                 & 70              & 67      \\ 
  {sun}              & {27.1}         & 672                                   & 453                                 & 278                & 93       \\ 
  {enron}            & 53.8            & 807                                   & 1257                                 & 2253            & {66}     \\ 
  trevi               & 231            & 829                                   & 2288                                 & 1812             & {96}     \\
  {nuswide}          & {64.5}          & 2283                                   & 1175                                 & 454                & 175      \\ 
  {notre}            & {26}         & 2827                                   & 419                                 & 208                & 264      \\ 
  {sift}             & {71.4}          & 8452                                       & 1252                                 & 624              & 786     \\ 
\bottomrule
\end{tabular}
\end{table}

\begin{table}[ht]\small
\centering
\setstretch{1.5}
\bicaption{索引构建时间对比}{Comparison of Indexing Time (ms)}
\label{tab:IndexingTime}
\begin{tabular}{c c c c c c}
\toprule
    & \textbf{d-HCTree}         &    \textbf{SRS}              &        \textbf{HD-Index}           &        \textbf{Flann}       &        \textbf{OASIS}             \\ \hline
\textbf{Complexity}     & $O(ndI)$       &  $O(n)$    & $O(mn)$                  & $O(ndI)$            & $O(nd+n\log n)$         \\ 
  {audio}            & 6.1           & {1.1}               & 180                       & 2.5               & 9.1                     \\ 
  {sun}              & 25          & {4.4}               & 539                       & 9.3                & 10.9                    \\ 
  {enron}            & 67          & {12.7}              & 946                       & 28.3               & 26.1                   \\ 
  trevi            & 121         & {32.0}                & 3195                      & 85.1               & 346.5                   \\ 
  {nuswide}          & 352         & {13.0}              & 729                       & 32.4               & 32.3                    \\ 
  {notre}            & 80          & {3.6}               & 379                       & 12.0               & 31.0                      \\ 
  {sift}             & 295         & {15.0}                & 1143                      & 37.4               & 96.6                    \\ 
\bottomrule
\end{tabular}
\end{table}

\subsubsection{索引构建时间}
表~\ref{tab:IndexingTime}报告了索引时间复杂度(理论和实际)的比较。从实证结果可以看出，HD-Index构建索引结构花费的时间最长，SRS构建索引结构花费的时间最短。其中d-HCTree、SRS和Flann构建索引结构花费的时间复杂度在数量级上相同。本章提出的d-HCTree和Flann在构建索引结构上的时间复杂度相同，有着良好的可扩展性。

\subsection{本章小结}
本章通过边缘聚类算法构建出用于支持$k$近邻查询的索引结构HCTree，并分析了索引结构的空间复杂度及构建的时间复杂度。基于HCTree提出了两种搜索方法:贪婪搜索和束搜索，并提出了索引结构的更新方法。最后本章提出了继续基于历史查询的索引优化方式，在多个真实的、公开的数据集上都取了较为优异的表现。
\newpage
